package class38;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class MaxSubSeqNum {

    public static int  maxSubSeqNum(String s,String t){
        if((s == null && t == null) || ("".equals(s) && "".equals(t))){
            return 1;
        }
        if((s == null && t != null) || s.length() < t.length()){
            return 0;
        }

        char[] sA = s.toCharArray();
        char[] tA = t.toCharArray();
        int[][] dp = new int[s.length()][t.length()];
        dp[0][0] = sA[0] == tA[0] ? 1 : 0;
        // dp[0][j] 其他不用填默认0
        // 列
        for (int i = 1; i < sA.length; i++) {
            dp[i][0] = sA[i] == tA[0] ?  dp[i-1][0] + 1 : dp[i-1][0];
        }


        for (int i = 1; i < sA.length; i++) {
            for (int j = 1; j < tA.length; j++) {
                dp[i][j] = dp[i-1][j] + (sA[i] == tA[j] ? dp[i-1][j-1] : 0);
            }
        }

        return dp[sA.length-1][tA.length-1];
    }

    public static void main(String[] args) {
        String s = "abcvcabc";
        String t = "abc";
        System.out.println(maxSubSeqNum(s,t));
    }
}
